package leetcode.code787.CheapestFlightsWithinKStops;

import java.util.HashMap;
import java.util.Map;

public class Solution78701 extends CheapestFlightsWithinKStops {

	@Override
	public int findCheapestPrice(int n, int[][] flights, int src, int dst, int k) {
		Map<Integer, Map<Integer, Integer>> map = new HashMap<>();
		for (int[] flight : flights) {
			if (map.containsKey(flight[0])) {
				Map<Integer, Integer> temp = map.get(flight[0]);
				temp.put(flight[1], flight[2]);
			} else {
				Map<Integer, Integer> temp = new HashMap<>();
				temp.put(flight[1], flight[2]);
				map.put(flight[0], temp);
			}
		}
		Integer[][][] cache = new Integer[n][n][k + 1];
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < n; j++) {
				for (int m = 0; m <= k; m++) {
					cache[i][j][m] = -1;
				}
			}
		}
		Integer result = this.fly(map, src, dst, k, 0, cache);
		return result == null ? -1 : result;
	}

	private Integer fly(Map<Integer, Map<Integer, Integer>> map, int src, int dst, int k, int times,
			Integer[][][] cache) {
		if (cache[src][dst][times] == null || cache[src][dst][times] != -1)
			return cache[src][dst][times];
		Map<Integer, Integer> srcMap = map.get(src);
		if (srcMap == null) {
			cache[src][dst][times] = null;
			return null;
		}
		if (k == times) {
			if (!srcMap.containsKey(dst)) {
				cache[src][dst][times] = null;
				return null;
			}
			else {
				cache[src][dst][times] = srcMap.get(dst);
				return cache[src][dst][times];
			}
		}
		Integer min = null;
		for (Integer to : srcMap.keySet()) {
			if (to == dst) {
				if (min == null)
					min = Integer.MAX_VALUE;
				min = Math.min(srcMap.get(dst), min);
			} else {
				Integer next = this.fly(map, to, dst, k, times + 1, cache);
				if (next != null) {
					int value = srcMap.get(to);
					int price = value + next;
					if (min == null)
						min = Integer.MAX_VALUE;
					min = Math.min(min, price);
				}
			}
		}
//		if (min != null) {
		cache[src][dst][times] = min;
//		}
//		else {
//			cache[src][dst][times] = Integer.MAX_VALUE;
//		}
		return min;
	}

	public static void main(String[] args) {
		Solution78701 so = new Solution78701();
//		so.debug1();
//		so.debug2();
//		so.debug3();
//		so.debug4();
		so.debug5();

	}

}
